
#include <assert.h>
#include <stdlib.h>

typedef char Item;
typedef struct PQnode* PQlink;
typedef struct pq* PQ;

struct PQnode {
    Item key;
    PQlink l;
    PQlink r;
};

struct pq {
    PQlink *bq;
};

#define maxBQsize 5
#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)

static PQlink z = NULL;

/////////////////////////////////接口操作////////////////////////////////////
PQ PQinit();
PQlink PQinsert(PQ pq, Item v);
Item PQdelmax(PQ pq);
void PQjoin(PQ a, PQ b);


///////////////////////////////////辅助函数/////////////////////////////////
PQlink pair(PQlink p, PQlink q);
void BQjoin(PQlink *a, PQlink *b);

//////////////////////////////////测试用例/////////////////////////////////
void test_pair();
void test_insert();
void test_insert2();
void test_join_carry();
void test_join_no_carry();
void test_delmax();

int main(int argc, char *argv[]) {
    // test_insert();
    // test_insert2();
    // test_join_carry();
    // test_join_no_carry();
    // test_pair();
    test_delmax();
    return 0;
}

PQ PQinit() {
    PQ pq = (PQ)malloc(sizeof(*pq));
    pq->bq = (PQlink *)malloc(maxBQsize * sizeof(PQlink));

    int i;
    for (i = 0; i < maxBQsize; i++) {
        pq->bq[i] = z;
    }

    return pq;
}

PQlink PQinsert(PQ pq, Item v) {
    PQlink t = malloc(sizeof(*t));
    PQlink c = t;
    c->key = v;
    c->l = z;
    c->r = z;
    int i;

    for (i = 0; i < maxBQsize; i++) {
        if (c == z) {
            break;
        }
        if (pq->bq[i] == z) {
            pq->bq[i] = c;
            break;
        }
        c = pair(c, pq->bq[i]);
        pq->bq[i] = z;

    }

    return t;
}

/**
* Program 9.15 Deletion of the maximum in a binomial queue
* ---------------------------------------------------------------------------------------------------------
First, we scan the root nodes to find the maximum, and
remove the power-of-2 heap containing the maximum from the binomial queue.

Then, we remove the root node containing the maximum from its power-of-2 heap and
temporarily build a binomial queue that contains the remaining constituent parts of the power-of-2 heap.

Finally, we use the `join` operation to merge this binomial queue back into the original binomial queue.
 */
Item PQdelmax(PQ pq) {
    int i;
    int max;
    PQlink x;
    Item v;
    PQlink temp[maxBQsize];

    for (i = 0, max = -1; i < maxBQsize; i++) {
        if (pq->bq[i] != z) {
            if ((max == -1) || (v < pq->bq[i]->key)) {
                max = i;
                v = pq->bq[max]->key;
            }
        }
    }

    x = pq->bq[max]->l;
    for (i = max; i < maxBQsize; i++) {
        temp[i] = z;
    }
    for (i = max; i > 0; i--) {
        temp[i-1] = x;
        x = x->r;
        temp[i-1]->r = z;
    }

    free(pq->bq[max]);
    pq->bq[max] = z;

    BQjoin(pq->bq, temp);
    return v;
}

void PQjoin(PQ a, PQ b) {
    BQjoin(a->bq, b->bq);
}

PQlink pair(PQlink p, PQlink q) {
    if (p->key < q->key) {
        p->r = q->l;
        q->l = p;
        return q;
    }else {
        q->r = p->l;
        p->l = q;
        return p;
    }
}

/**
 * Program 9.16 Joining (merging) of two binomial queues
 * -------------------------------------------------------------------------
 * This code mimics the operation of adding two binary numbers.
 *
 * Proceeding from right to left with an initial carry bit of 0,
 * we treat the eight possible cases (all possible values of the operands and carry bits) in a straightforward manner.
 *
 * For example, case 3 corresponds to the operand bits being both 1 and the carry 0. Then, the result is 0,
 * but the carry is 1 (the result of adding the operand bits).
 *
 * #define test(C, B, A) 4*(C) + 2*(B) + 1*(A)
 */
void BQjoin(PQlink *a, PQlink *b) {
    int i;
    PQlink c = z;
    for (i = 0; i < maxBQsize; i++) {
        switch (test(c != z, b[i] != z, a[i] != z)) {
            case 2:
                a[i] = b[i];
                break;
            case 3:
                c = pair(a[i], b[i]);
                a[i] = z;
                break;
            case 4:
                a[i] = c;
                c = z;
                break;
            case 5:
                c = pair(c, a[i]);
                a[i] = z;
                break;
            case 6:
            case 7:
                c = pair(c, b[i]);
                break;
            default:
                break;
        }
    }
}


//////////////////////////////////测试用例/////////////////////////////////

/**
* Figure 9.15 A binomial queue of size 13
* -------------------------------------------------
* A binomial queue of size N is a list of left-heap-ordered power-of-2 heaps,
* one for each bit in the binary representation of N.
* Thus, a binomial queue of size 13 = 1101_2 consists of an 8-heap, a 4-heap, and a 1-heap.
*
*/
void test_insert() {
    PQ pq = PQinit();
    // A-S-O-R-T-I-N-G-E-W-P-L-E
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQinsert(pq, 'O');
    PQinsert(pq, 'R');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'N');
    PQinsert(pq, 'G');
    PQinsert(pq, 'E');
    PQinsert(pq, 'W');
    PQinsert(pq, 'P');
    PQinsert(pq, 'L');
    PQinsert(pq, 'E');

    assert(pq->bq[0]->key == 'E');
    assert(pq->bq[1] == z);
    assert(pq->bq[2]->key == 'W');
    assert(pq->bq[2]->r == z);
    assert(pq->bq[2]->l->key == 'P');
    assert(pq->bq[2]->l->l->key == 'L');
    assert(pq->bq[2]->l->r->key == 'E');
    assert(pq->bq[3]->key == 'T');
    assert(pq->bq[3]->r == z);
    assert(pq->bq[3]->l->key == 'S');
    assert(pq->bq[3]->l->l->key == 'R');
    assert(pq->bq[3]->l->r->key == 'N');
    assert(pq->bq[3]->l->l->l->key == 'O');
    assert(pq->bq[3]->l->l->r->key == 'A');
    assert(pq->bq[3]->l->r->l->key == 'G');
    assert(pq->bq[3]->l->r->r->key == 'I');
}

/**
* Figure 9.16 Joining of two equal-sized power-of-2 heaps.
* -----------------------------------------------------------
* We join two power-of-two heaps (top) by putting the larger of the roots at the root,
* with that root’s (left) subtree as the right subtree of the other original root.
* If the operands have 2^n nodes, the result has 2^{n+1} nodes.
* If the operands are left-heap ordered, then so is the result, with the largest key at the root.
 */
void test_pair() {
    // A-S-O-R-T-I-N-G
    PQ pq = PQinit();
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQinsert(pq, 'O');
    PQinsert(pq, 'R');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'N');
    PQinsert(pq, 'G');
    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2] == z);
    assert(pq->bq[3]->key == 'T');

    // E-X-A-M-P-L-E-W
    PQ pq2 = PQinit();
    PQinsert(pq2, 'E');
    PQinsert(pq2, 'X');
    PQinsert(pq2, 'A');
    PQinsert(pq2, 'M');
    PQinsert(pq2, 'P');
    PQinsert(pq2, 'L');
    PQinsert(pq2, 'E');
    PQinsert(pq2, 'W');
    assert(pq2->bq[0] == z);
    assert(pq2->bq[1] == z);
    assert(pq2->bq[2] == z);
    assert(pq2->bq[3]->key == 'X');

    pair(pq->bq[3], pq2->bq[3]);

    assert(pq2->bq[3]->key == 'X');
    assert(pq2->bq[3]->l->key == 'T');
    assert(pq2->bq[3]->r == z);
    assert(pq2->bq[3]->l->l->key == 'S');
    assert(pq2->bq[3]->l->r->key == 'W');
}

/**
* Figure 9.17 Insertion of a new element into a binomial queue
* ---------------------------------------------------------------
* Adding an element to a binomial queue of seven nodes is analogous to performing
* the binary addition 111_2 + 1 = 1000_2, with carries at each bit.
* The result is the binomial queue at the bottom, with an 8-heap and null 4-, 2-, and 1-heaps.
*/
void test_insert2() {
    PQ pq = PQinit();
    // P-L-E-W-T-I-E
    PQinsert(pq, 'P');
    PQinsert(pq, 'L');
    PQinsert(pq, 'E');
    PQinsert(pq, 'W');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'E');
    // N
    PQinsert(pq, 'N');

    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2] == z);
    assert(pq->bq[3]->key == 'W');
    assert(pq->bq[3]->r == z);
    assert(pq->bq[3]->l->key == 'T');
    assert(pq->bq[3]->l->l->key == 'N');
    assert(pq->bq[3]->l->r->key == 'P');
    assert(pq->bq[3]->l->l->l->key == 'E');
    assert(pq->bq[3]->l->l->r->key == 'I');
    assert(pq->bq[3]->l->r->l->key == 'L');
    assert(pq->bq[3]->l->r->r->key == 'E');

}

/**
* Figure 9.18 Deletion of the maximum in a power-of-2 heap
* -----------------------------------------------------------
* Taking away the root gives a forest of power-of-2 heaps, all left-heap ordered,
* with roots from the right spine of the tree.
*
* This operation leads to a way to delete the maximum element from a binomial queue:
* - Take away the root of the power-of-2 heap that contains the largest element,
* - then use the join operation to merge the resulting binomial queue with
*   remaining power-of-2 heaps in the original binomial queue.
*/
void test_delmax() {
    PQ pq = PQinit();
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQinsert(pq, 'O');
    PQinsert(pq, 'R');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'N');
    PQinsert(pq, 'G');
    PQinsert(pq, 'E');
    PQinsert(pq, 'X');
    PQinsert(pq, 'A');
    PQinsert(pq, 'M');
    PQinsert(pq, 'P');
    PQinsert(pq, 'L');
    PQinsert(pq, 'E');
    PQinsert(pq, 'W');

    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2] == z);
    assert(pq->bq[3] == z);
    assert(pq->bq[4]->key == 'X');

    PQdelmax(pq);
    assert(pq->bq[0]->key == 'E');
    assert(pq->bq[1]->key == 'M');
    assert(pq->bq[2]->key == 'W');
    assert(pq->bq[3]->key == 'T');


}

/**
* Figure 9.19 Joining of two binomial queues (no carry)
* ------------------------------------------------------------------------
* When two binomial queues to be joined do not have any power-of-2 heaps of the same size,
* the join operation is a simple merge.
*
* Doing this operation is analogous to adding two binary numbers without ever encountering 1 + 1 (no carry).
*
* Here, a binomial queue of 10 nodes is merged with one of 5 nodes to make one of 15 nodes,
* corresponding to 1010_2 + 0101_2 = 1111_2.
*/
void test_join_no_carry() {
    // 队列1：A->S->O->R->T->I->N->G->A->M
    PQ pq1 = PQinit();
    PQinsert(pq1, 'A');
    PQinsert(pq1, 'S');
    PQinsert(pq1, 'O');
    PQinsert(pq1, 'R');
    PQinsert(pq1, 'T');
    PQinsert(pq1, 'I');
    PQinsert(pq1, 'N');
    PQinsert(pq1, 'G');
    PQinsert(pq1, 'A');
    PQinsert(pq1, 'M');
    assert(pq1->bq[0] == z);
    assert(pq1->bq[2] == z);
    assert(pq1->bq[1]->key == 'M');
    assert(pq1->bq[1]->r == z);
    assert(pq1->bq[1]->l->key == 'A');
    assert(pq1->bq[3]->key == 'T');
    assert(pq1->bq[3]->r == z);
    assert(pq1->bq[3]->l->key == 'S');
    assert(pq1->bq[3]->l->l->key == 'R');
    assert(pq1->bq[3]->l->r->key == 'N');
    assert(pq1->bq[3]->l->l->l->key == 'O');
    assert(pq1->bq[3]->l->l->r->key == 'A');
    assert(pq1->bq[3]->l->r->l->key == 'G');
    assert(pq1->bq[3]->l->r->r->key == 'I');

    // 队列2：E->W->P->L->E
    PQ pq2 = PQinit();
    PQinsert(pq2, 'E');
    PQinsert(pq2, 'W');
    PQinsert(pq2, 'P');
    PQinsert(pq2, 'L');
    PQinsert(pq2, 'E');
    assert(pq2->bq[1] == z);
    assert(pq2->bq[3] == z);
    assert(pq2->bq[0]->key == 'E');
    assert(pq2->bq[2]->key == 'W');
    assert(pq2->bq[2]->r == z);
    assert(pq2->bq[2]->l->key == 'P');
    assert(pq2->bq[2]->l->l->key == 'L');
    assert(pq2->bq[2]->l->r->key == 'E');

    PQjoin(pq2, pq1);
    assert(pq2->bq[0]->key == 'E');
    assert(pq2->bq[1]->key == 'M');
    assert(pq2->bq[2]->key == 'W');
    assert(pq2->bq[3]->key == 'T');
    assert(pq2->bq[1]->r == z);
    assert(pq2->bq[1]->l->key == 'A');
    assert(pq2->bq[2]->r == z);
    assert(pq2->bq[2]->l->key == 'P');
    assert(pq2->bq[2]->l->l->key == 'L');
    assert(pq2->bq[2]->l->r->key == 'E');
    assert(pq2->bq[3]->r == z);
    assert(pq2->bq[3]->l->key == 'S');
    assert(pq2->bq[3]->l->l->key == 'R');
    assert(pq2->bq[3]->l->r->key == 'N');
    assert(pq2->bq[3]->l->l->l->key == 'O');
    assert(pq2->bq[3]->l->l->r->key == 'A');
    assert(pq2->bq[3]->l->r->l->key == 'G');
    assert(pq2->bq[3]->l->r->r->key == 'I');
}

/**
* Figure 9.20 Joining of two binomial queues
* --------------------------------------------------------------
* Adding a binomial queue of 3 nodes to one of 7 nodes gives one of 10 nodes through a process
* that mimics the binary addition 011_2 + 111_2 = 1010_2.
* Adding N to E gives an empty 1-heap in the result with a carry 2-heap containing N and E.
* Then adding the three 2-heaps leaves a 2-heap in the result with a carry 4-heap containing T N E I.
* This 4-heap is added to the other 4-heap, producing the binomial queue at the bottom.
*
* Few nodes are touched in the process.
*/
void test_join_carry() {
    // 队列1：I->T->N
    PQ pq1 = PQinit();
    PQinsert(pq1, 'I');
    PQinsert(pq1, 'T');
    PQinsert(pq1, 'N');
    assert(pq1->bq[0]->key == 'N');
    assert(pq1->bq[1]->key == 'T');
    assert(pq1->bq[1]->l->key == 'I');

    // 队列2： P->L->E->W->M->A->E
    PQ pq2 = PQinit();
    PQinsert(pq2, 'P');
    PQinsert(pq2, 'L');
    PQinsert(pq2, 'E');
    PQinsert(pq2, 'W');
    PQinsert(pq2, 'M');
    PQinsert(pq2, 'A');
    PQinsert(pq2, 'E');
    assert(pq2->bq[0]->key == 'E');
    assert(pq2->bq[1]->key == 'M');
    assert(pq2->bq[1]->l->key == 'A');
    assert(pq2->bq[1]->r == z);
    assert(pq2->bq[2]->key == 'W');
    assert(pq2->bq[2]->r == z);
    assert(pq2->bq[2]->l->key == 'P');
    assert(pq2->bq[2]->l->r->key == 'E');
    assert(pq2->bq[2]->l->l->key == 'L');

    PQjoin(pq2, pq1);
    assert(pq2->bq[0] == z);
    assert(pq2->bq[1]->key == 'M');
    assert(pq2->bq[1]->l->key == 'A');
    assert(pq2->bq[2] == z);
    assert(pq2->bq[3]->key == 'W');
    assert(pq2->bq[3]->r == z);
    assert(pq2->bq[3]->l->key == 'T');
    assert(pq2->bq[3]->l->l->key == 'N');
    assert(pq2->bq[3]->l->r->key == 'P');
    assert(pq2->bq[3]->l->l->l->key == 'E');
    assert(pq2->bq[3]->l->l->r->key == 'I');
    assert(pq2->bq[3]->l->r->l->key == 'L');
    assert(pq2->bq[3]->l->r->r->key == 'E');
}